package puzzle.projecteuler.p200;

public class Problem148B {

	/**
	 * 定义： f(n) = max {a: 7^a | n!}
	 * 显然： f(n) = [n/7] + [n/7^2] + ...
	 * 在7进制中，n的各位数码之和为d(n)，我们还有 f(n) = [n-d(n)]/6 
	 * C(m, n) 中因子7的次数是 f(m)-f(n)-f(m-n) 
	 * 
	 * 注意 ：f(m)=f(m-n)+f(n)
	 * 等价于d(m) = d(n)+d(m-n)
	 * 等价于(m-n)和n，在7进制下相加的过程中不发生进位。
	 * 
	 * 如果在7进制下，m = m1...mk
	 * 那么满足条件的n有(m1+1)*..*(mk+1)个
	 * 
	 * 再继续分析，可以知道
	 * sigma (m1+1)*..*(mk+1)， 对所有小于等于M的整数 m = (m1...mk)7 求和
	 * 假设M = (M1...Mk)7
	 * 我们记为：g(M) = g(M1...Mk) = C(M1+1,2)*28^(k-1) + (M1+1)*g(M2...Mk)
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		
		long M = 1000000000;
		String n7 = Long.toString(M, 7);
		long n28 = g(n7);
		System.out.println(n28);
	}
	
	public static long g(String M) {
		if (M.length() == 1) {
			long M1 = M.charAt(0) - '0';
			return (M1+1)*M1/2;
		} else {
			long M1 = M.charAt(0) - '0';
			long k = M.length();
			M = M.substring(1);
			return (M1+1)*M1/2 * (long)Math.pow(28, k-1) + (M1+1)*g(M);
		}
	}

}
